package 双指针;

public class 删除排序链表中的重复元素 {
    //双指针解法
    public ListNode deleteDuplicates1(ListNode head) {
        if (head==null)
            return null;
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode preNode = head,prePreNode = dummyNode,tmp = head.next;
        while (tmp!=null){
            if (preNode.val==tmp.val){
                while (tmp!=null){
                    if (tmp.val != preNode.val)
                        break;
                    tmp = tmp.next;
                }
                prePreNode.next = tmp;
                preNode = tmp;
                if (tmp!=null)
                    tmp = tmp.next;
                continue;
            }
            prePreNode = preNode;
            preNode = tmp;
            tmp = tmp.next;
        }
        return dummyNode.next;
    }

    //递归解法
    public ListNode deleteDuplicates(ListNode head) {
        //baseCase
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        if (head.val == next.val) {
            while (next != null && head.val == next.val) {
                next = next.next;
            }
            head = deleteDuplicates(next);
        } else {
            head.next = deleteDuplicates(next);
        }
        return head;
    }
}
